package com.mj.listen1._11_哈希表.map;

import java.util.Objects;

/**
 * 对原来的哈希表中的红黑树增加双向列表
 *
 * @param <K>
 * @param <V>
 */
public class LinkedHashMap<K, V> extends HashMap<K, V> {

    private LinkNode<K, V> first;
    private LinkNode<K, V> last;

    @Override
    protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        LinkNode<K, V> node = new LinkNode<>(key, value, parent);
        // 双向链表，添加线
        if (first == null) {
            // 第一次添加节点
            first = last = node;
        } else {
            // 非第一次添加节点
            last.next = node;
            node.pre = last;
            last = node;
        }
        return node;
    }

    @Override
    protected void afterRemove(Node<K, V> willRemoveNode, Node<K, V> realRemoveNode) {

        LinkNode<K, V> node1 = (LinkNode<K, V>) willRemoveNode;
        LinkNode<K, V> node2 = (LinkNode<K, V>) realRemoveNode;

        if (node1 != node2) {// node1要删除节点，node2为node1的后继节点
            // 度为2的节点，需要交换链表的pre、next。转换为node1和node2两个节点的交换
            // 交换pre
            LinkNode<K, V> temp = node1.pre;
            node1.pre = node2.pre;
            node2.pre = temp;
            if (node1.pre != null) {
                node1.pre.next = node1;
            } else {
                first = node1;
            }

            if (node2.pre != null) {
                node2.pre.next = node2;
            } else {
                first = node2;
            }

            // 交换next
            temp = node1.next;
            node1.next = node2.next;
            node2.next = temp;
            if (node1.next != null) {
                node1.next.pre = node1;
            } else {
                last = node1;
            }

            if (node2.next != null) {
                node2.next.pre = node2;
            } else {
                last = node2;
            }
        }


        // 节点断线删除
        LinkNode<K, V> pre = node2.pre;
        LinkNode<K, V> next = node2.next;
        if (pre == null) {
            // 删除的是头节点
            first = next;
        } else {
            pre.next = next;
        }

        if (next == null) {
            // 删除的是尾节点
            last = pre;
        } else {
            next.pre = pre;
        }
    }

    @Override
    public void clear() {
        super.clear();
        first = last = null;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {
        if (visitor == null) return;
        LinkNode<K, V> node = first;
        while (node != null) {
            if (visitor.visit(node.key, node.value)) return;
            // 指向链表的下一个节点
            node = node.next;
        }
    }

    @Override
    public boolean containsValue(V value) {
        // 遍历链表
        LinkNode<K, V> node = first;
        while (node != null) {
            if (Objects.equals(value, node.value)) return true;
            node = node.next;
        }
        // 没有找到
        return false;
    }

    private static class LinkNode<K, V> extends Node<K, V> {
        LinkNode<K, V> pre;
        LinkNode<K, V> next;

        public LinkNode(K key, V value, Node<K, V> parent) {
            super(key, value, parent);
        }
    }
}
